Problèmes de plus court chemin : l'algorithme de Dijkstra

L’algorithme proposé pour résoudre ce type de problème est l’algorithme de Dijkstra (ou Dijkstra-Moore).

Propriété Déroulement de l‘algorithme de Dijkstra

On cherche le plus court chemin entre une origine  \(D\) (pour « départ ») et un autre sommet du graphe ; nous allons calculer progressivement dans un tableau pour chaque sommet le poids du plus court chemin y conduisant depuis l’origine.

1. Initialisation. On fixe la marque de  \(D\) à \(0\) , et on marque provisoirement chacun des sommets
adjacents à  \(D\) par le poids de l’arête correspondante. On marque les autres sommets, non
adjacents, par \(\infty\) .

2. Marquage. On regarde tous les sommets de marque non fixée et on repère celui qui a la plus petite marque, que l’on fixe ; on note  \(X\) ce sommet.

3. Exploration. Pour chaque sommet  \(Y\) de marque non fixée adjacent à \(X\) , on calcule la somme de la marque de  \(X\) avec le poids de l’arrête reliant  \(X\) à \(Y\) .

4. Décision. Si cette somme est inférieure à la marque de \(Y\) , on remplace la marque de  \(Y\) par cette somme en indiquant entre parenthèses la provenance de cette nouvelle marque optimale.

5. Itération. On recommence à partir de l’étape \(2\) , jusqu’à avoir parcouru tous les sommets et exploré tout le graphe.

6. Fin de l’algorithme. Toutes les marques étant optimales, la marque fixée du sommet  \(Y\) est le poids d’une plus courte chaîne reliant  \(D\) à \(Y\) .

Remarques

Pour une convergence plus rapide, on considère qu’on a déjà simplifié le graphe pondéré en « supprimant » tous les sommets qui sont de degré  \(2\) s’ils ne sont pas l’origine ou la destination de chemin recherché (on a additionné les poids des arêtes correspondantes et supprimé les sommets en « impasses » s’ils ne sont pas l’origine ou la destination de chemin recherché.

D’un point de vue pratique, on peut placer les itérations dans un tableau, ce qui permet une relecture facile du chemin trouvé.

Le chemin trouvé n’est pas obligatoirement unique ; son poids est le plus faible mais il pourrait y avoir un autre chemin de même poids.

Si le graphe n’est pas connexe et qu’il n’existe pas de chaîne reliant les sommets pour lesquels on cherche le plus court chemin, au bout d’un temps fini l’algorithme n’explore plus de nouveaux sommets, il y a donc blocage.

Efficacité de cet algorithme : si le graphe est d’ordre  \(n\) le nombre d’étapes est d’ordre \(n^2\) , alors que l’algorithme naïf qui consiste à comparer tous les chemins est en général exponentiel en \(n\) , et donc déjà inutilisable pour des graphes à \(50\)  ou \(100\)  sommets.